A. Relaxation Process
The relaxation process is a technique for using contextual information to reduce local ambiguity and achieve global consistency. The relaxation process has been applied successfully to a variety of image processing tasks such as scene labeling (see e.g., A. Rosenfeld, R. A. Hummel, and S. W. Zucker, "Scene Labeling by Relaxation Operations," IEEE Trans. on System, Man, and Cybernetics, SMC-6:420-433, June 1976; S. W. Zucker, E. V. Krishnamurthy, and R. L. Haar, "Relaxation Processes for Scene Labeling: Convergence, Speed, and Stability," IEEE Trans. on System, Man, and Cybernetics, SMC-8:41-48, January 1978), shape matching (see e.g., B. Bhanu and O. D. Faugeras, "Shape Matching of 2-d Object Using a Hierarchical Stochastic Labeling Technique," In Proc. of Conf. on Pattern Recognition and Image Proc., pages 688-690, Las Vegas, Nev., June 1982 and C. Wang, H. Sun, S. Yada, and A. Rosenfeld, "Some Experiments in Relaxation Image Matching Using Corner Features," Pattern Recognition, 16:167-182, 1983) handwritten character recognition (see e.g., H. Ogawa and K. Taniguchi, "On Machine Recognition of Hand-printed Chinese Characters by Feature Relaxation," Pattern Recognition, 21:1-7, 1988 and I. Sekita, K. Toraichi, R. Mori, K. Yamamoto, and H. Yamada, "Feature Extraction of Hand-written Japanese Characters by Spline Functions for Relaxation," Pattern Recognition, 21:9-17, 1988) and thinning (see e.g., Shiaw-Shian Yu and Wen-Hsiang Tsai, "A New Thinning Algorithm for Gray-Scale Images by the Relaxation Technique," Pattern Recognition, 23(10):1067-1076, 1990).
There are three types of relaxation processes: discrete relaxation, fuzzy relaxation, and probabilistic relaxation. The present invention is concerned with probabilistic relaxation, which is discussed in detail in Azriel Rosenfeld and Avinash C. Kak, "Digital Picture Processing", Second Edition Volume 2, Academic Press, 1982 pp 152-187.
The probabilistic relaxation precess is as follows.
Suppose that there is a set of n objects A.sub.1, . . . , A.sub.n that are to be classified into m classes C.sub.1, . . . ,C.sub.m. (Illustratively, in an image processing application, the objects are pixels and the classes are gray scales.) Suppose further that the class assignments of the objects are interdependent: in other words, for each pair of class assignments A.sub.i .epsilon.C.sub.j and A.sub.n .epsilon.C.sub.k, there is a quantitative measure of the compatibility of this pair, which is denoted by c(i,j; h,k). For concreteness, it may be assumed that positive values of c(i,j; h,k) represent compatibility of A.sub.i .epsilon.C.sub.j with A.sub.h .epsilon.C.sub.k ; negative values represent incompatibility; and zero represents "don't care."It may be further assumed that the c's (i.e., the compatibilities) always lie in some fixed range, say [-1,1]. Note that the c's need not be symmetric, i.e., it is not necessary that c(i,j; h,k)=c(h,k;i,j).
Let p.sup.(0) ij be an initial estimate of the probability that A.sub.i .epsilon.C.sub.j, 1.ltoreq.i.ltoreq.n,1.ltoreq.j.ltoreq.m. Thus for each value of i we have 0&lt;p.sup.(0) in.ltoreq.1 and ##EQU1## There is now described an iterative method of computing successive "probability estimates" p.sup.(r) in,r=1,2, . . . , based on the initial probabilities and the compatibilities. These successively calculated p's are called probability estimates because they satisfy 0.ltoreq.p.sup.(r).sub.ij .ltoreq.1 and ##EQU2## for each i and r.
Consider how p.sub.ij should be adjusted at each iteration step, based on the current values of the other p's and on the values of the c's. Intuitively, if p.sub.hk is high and c(i,j;h,k) is positive, we want to increase P.sub.inj, since it is compatible with the high-probability event A.sub.h .epsilon.C.sub.k. Similarly, if p.sub.hk is high and c(i,j;h,k) is negative, we want to decrease p.sub.ij, since it is incompatible with A.sub.h .epsilon.C.sub.k, which has high probability. On the other hand, if p.sub.hk is low, or if c(i,j; h,k) is near zero, we do not want to change p.sub.hk very much, since A.sub.h .epsilon.C.sub.k either has low probability, or is essentially irrelevant to A.sub.i .epsilon.C.sub.j. A very simple way of defining an increment to p.sub.ij that has these desired properties is to use the product c(i,j; h,k)p.sub.hk.
How should these increments be combined for all the h's and k's? The simplest way of doing this is to linearly combine them. For each object A.sub.h, the increments are summed over all the possible classes C.sub.k, i.e. ##EQU3## This sum will be positive if the high-probability C.sub.k 's for A.sub.h are compatible with A.sub.i .epsilon.C.sub.j, negative if they are incompatible, and near zero if they are irrelevant. Note that this sum is still in the range [-1,1] since ##EQU4## . These net increments can then be averaged for all objects A.sub.h .noteq.A.sub.i, i.e., there is computed: This too is still in the range [-1,1].
The increment q.sub.ij is now applied in order to obtain new estimates for p.sub.ij. It is desirable for the new estimates to be nonnegative and to satisfy ##EQU5## . A simple way of insuring nonnegativeness is to multiply p.sub.ij by 1+q.sub.ij ; this quantity is nonnegative, since q.sub.ij .gtoreq.-1. Note that if q.sub.ij is negative, P decreases, and if positive, it increases, as desired. Finally, the new estimates of p.sub.ij are normalized by dividing each of them (for a given i) by their sum; this insures that the p.sub.ij's for a given i sum to 1. The incrementation process is thus defined by Note that if any p.sup.(r) is 0, it can never become nonzero, and if it is 1, it cannot change.
The relaxation process operates as follows. Initial estimates of the probabilities p.sub.ik are determined as well as estimates of the compatibilities. The system then evolves in time according to equations (3) and (4). Each p.sub.ij eventually reaches the value of one or zero indicating definitively whether or not the object A.sub.i is in the class C.sub.j.
As an example of the relaxation process, consider how the relaxation process might be applied to classifying pixels into dark and light classes based on their gray levels, i.e., to thresholding. This example is especially simple for two reasons:
1) There are only two classes 1 and 0, corresponding to object and background gray levels.
2) The compatibilities between neighboring pairs of points should all be alike, independent of direction, unless the picture is directionally biased.
Thus, for each pixel A.sub.x,y, with coordinates x and y, there are only two probabilities p.sub.(x,y)0 and p.sub.(x,y)1 where p(.sub.x,y)1=1-p.sub.(x,y)0. Moreover, for each pixel A.sub.x,y and any of its eight neighboring pixels, with coordinates u, v, there are only four compatibilities c((x,y,0;(u,v),0),c((x,y),0;(u,v),1) c((x,y),1;(u,v),0) and c((x,y),1,(u,v),1). All other compatibilities are assumed to be zero in this example.
To assign an initial probability values to each pixel, the following scheme may be utilized (see e.g. A. Rosenfeld and R. C. Smith, "Thresholding Using Relaxation", IEEE Transactions On Pattern Analysis and Machine Intelligence, PAMI-3:508-606, 1981) Let G.sub.x,y be the gray level of pixel A.sub.x,y, m be the mean gray level, and let O and B be the gray levels corresponding to object and background, then it is defined: ##EQU6##
A general method of defining compatibility coefficients based on the mutual information of the classes at neighboring pixels was proposed in S. Peleg et al, "Determining Compatibility Coefficients for Curve Enhancement Relaxation Processes", IEEE Trans. on Systems, Man and Cybernetics, SMC 8:548-555 July 1978.
Once the initial probability estimates P.sup.(0) (x,y) and P(0).sub.(x,y)0 are obtained and values for the compatibility coefficients are obtained, the iterations of the probabilities are calculated according to equations (3) and (4) until each probability reaches a value of zero or one which determines definitively whether the corresponding pixel has the object gray scale value 0 or the background gray scale value B.